#第四章 快速排序

#先熟悉分治思想
def sum_ary(ary):        
    if len(ary)==0:
        return 0   
    return ary[0] + sum_ary(ary[1:])
    
s = sum_ary([2,4,6]) #通过递归把一个数组里的元素拆开成一个个单独的数字然后求和

print("s=",s)

def cal_len(ary):
    if ary == []:
        return 0    
    return 1 + cal_len(ary[1:])

print('cal_len',cal_len([2,3,4]))

#快速排序
'''
1.选择基准值
2.分区:
    a.先从右边开始找出第一个小于基准的值，确定右半区的分界点
    b.再从左边开始找出第一个大于基准的值，确定左半区分界点
3.对分区数组执行1,2步骤直到数组无法分区
'''
#递归实现快速排序
def quick_sort(ary):    
    if len(ary)  < 2: #只有一个元素的数组就是有序的，不能再分组了
        return ary
    else:
        pivot = ary[0] #选择基准值 一般是第一个元素
        left_ary = [i for i in ary[1:] if i<=pivot] #分区：左边的比基准值小
        right_ary = [i for i in ary[1:] if i>pivot] #分区 右边的比基准值大
        return quick_sort(left_ary) + [pivot] + quick_sort(right_ary) #再次进行分区 把分区的结果合并在一起就是有序的数组了

print(quick_sort([2,1,3,5,4,7,5,8,9,3,5]))

#网上的快排版本
'''
同样是分治思想 
分别从数组的两端开始搜索把所有小于基准值的移动到左边大于的移动到右边
'''

'''
百度百科版本
https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842?fr=aladdin&fromid=2084344&fromtitle=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F#3_13
'''
def quickSort(L, low, high):
    i = low 
    j = high
    if i >= j:
        return L
    key = L[j]
    while i < j:
        while i < j and L[j] >= key:
            j = j-1                                                             
        L[i] = L[j]
        while i < j and L[i] <= key:    
            i = i+1 
        L[j] = L[i]
    L[i] = key 
    quickSort(L, low, i-1)
    quickSort(L, j+1, high)
    return L

#自己抄写写百度百科
def quick_sort2(ary,low,high):        
    i = low
    j = high    
    if i >= j:
        return    
    povit = ary[i] #通常是最小那个为基准值
    while i < j:  
        #从右边开始搜索找出第一个比基准值小的           
        while i < j and ary[j] >= povit: 
            j -= 1      
        ary[i] = ary[j] #并把找到的该值放在基准值的位置
        #从左边开始搜索找出第一个比基准值大的               
        while i < j and ary[i] <= povit:
            i += 1
        ary[j] = ary[i] #上次找到j的位置是第一个大于基准值的 所有这次找到大于的放在j的位置 
        
    ary[i] = povit #把基准值重设在找到的i的位置(因为经过上面的一次循环这个位置的左边都比基准值小)
    #开始分组执行快速排序
    quick_sort2(ary,low,i-1) # 对左半边进行排序       
    quick_sort2(ary,j+1,high) #对右边进行排序


ary = [6,2,7,3,8,9,5,4,1]
quick_sort2(ary,0,len(ary)-1)
print('快排结束了 ary=',ary)

import time
import random

c = 100
largeArr = list(range(c))
random.shuffle(largeArr)

def cost_test(fn,*args,n=1,msg='q1'):    
    for i in range(n):
        t0 = time.time()
        fn(largeArr,*args)
        t1 = time.time()
        print(msg," --- =",t1-t0)
    print("-----------------------")

cost_test(quick_sort,msg='q1')
cost_test(quick_sort2,0,c-1,msg='q2')

'''
经过测试对比 
同样是10万个元素的数组
百度百科的版本消耗比较大 需要9秒左右
而书中版本大概6秒完成排序
'''
        


    